package interview.dynamic;

import util.GsonUtil;

/**
 * 给一个 M x N 的数组矩阵，求从左上角到右下角路径的最小和
 * 举栗：
 * Input:
 * [
 *  [1,3,1],
 *  [1,5,1],
 *  [4,2,1]
 * ]
 * Output : 7 (因为最短路径是1-3-1-1-1)
 *
 * 要求：时间复杂度 = O(NxM)
 * 找递推公式：
 *
 * 假设:p(x,y) 为到这个点的最短路径
 * 则：p(m,n) = Math.min(p(m-1,n), p(m,n-1)) + grid[m,n]
 *
 * Created by yzy on 2021-02-05 16:37
 */
public class MinimumPathSum {

    public static void main(String[] args) {
        int[][] grip = new int[][]{{1,3,1},{1,5,1},{2,4,1}};
        minPathSum(grip);
    }

    public static int minPathSum(int[][] grid) {
        int h = grid.length;
        int w = grid[0].length;
        int[][] dp = new int[h][w];
        for(int i=0; i<h; i++){
            for(int j=0; j<w; j++){
                if(i==0 && j==0){
                    dp[i][j] = grid[i][j];
                }else if(i==0){
                    dp[i][j] = dp[i][j-1] + grid[i][j];
                }else if(j==0){
                    dp[i][j] = dp[i-1][j] + grid[i][j];
                }else{
                    dp[i][j] = Math.min(dp[i-1][j], dp[i][j-1]) + grid[i][j];
                }
            }
        }
        return dp[h-1][w-1];
    }
}
